1. Field of the Invention
The present invention relates, in general, to methods and systems for managing data storage in tables aid databases, and, more particularly, to methods and systems for mapping information in a tree structure, such as that found in an information directory to a relational database structure or relational table to facilitate searching and other data access using database management system techniques.
2. Relevant Background
In the data storage industry, there are many applications where data is stored in the form of an information directory. For example, information directories are particularly useful for storing information that is read often from many locations or many clients over a network and is updated infrequently. Examples of information that may be stored in information directories include: company employee information such as phone books, organization charts, and so on; external customer contact information; equipment or other inventories; and other sets of data that are readily optimized for read-intensive operations.
A commonly implemented information directory is a lightweight Directory Access Protocol (LDAP) directory. The LDAP is an application protocol for querying and modifying directory services running over TCP/IP. In LDAP, a directory is a set of objects with similar attributes organized in a logical and hierarchical manner. The most common example is a telephone directory, which includes a series of names (e.g., either of persons or organizations) organized alphabetically, with each name having an address and phone number attached. Due to this basic design, LDAP is often used by other services for authentication. LDAP directory servers store their data hierarchically in a tree structure with each node of the tree being a record or entry of the directory. An LDAP directory tree often reflects various political, geographic, and/or organizational boundaries, depending on the model chosen. LDAP deployments today tend to use Domain Name System (DNS) names for structuring the topmost levels of the hierarchy. Deeper inside the directory might appear entries representing people, organizational units, printers, documents, groups of people or anything else that represents a given tree entry or multiple entries.
FIG. 1 illustrates a block diagram of a conventional LDAP directory service system or network 100. According to the LDAP protocol, a client machine 110 makes a TCP/IP connection to an LDAP server 112 through network 111, sends requests, and receives responses. LDAP server 112 supports a directory 121 as illustrated in a simplified tree structure or form in FIG. 1. Each of the client and server machines further includes a directory runtime component 125 for implementing the directory service operations. The directory 121 is based on the concept of an entry 127, which contains information about some object (e.g., a person, a piece of inventory, and so on). Entries are composed of attributes 129, which have a type and one or more values. Each attribute 129 has a particular syntax that determines what kinds of values are allowed in the attribute (e.g., ASCII text, binary characters, and the like) and how these values are constrained during a particular directory operation. The directory tree 121 is organized in a predetermined manner with each entry uniquely named relative to its sibling entries by a relative distinguished name (RDN). An RDN comprises at least one distinguished attribute value from the entry 127, and one value from each attribute 129 is used in the RDN. According to the LDAP protocol, a globally unique name for an entry, referred to as a distinguished name (DN) includes a concatenation of the RDN sequence from a given entry to the tree root.
Further, in practice, the LDAP directory service model is based on object classes and represents data in a tree structure with each node being an entry complying width at least one object class. An object class is a collection of attributes that describes it, and each attribute has a name, type, and one or more values. For example, attributes describing a person might include a personas name (common name, or “cn”, telephone number, and email address. An entry is an instantiation of one or more object classes. An entry is a collection of attributes that has a name, called a distinguished name (DN). The DN is used to refer to the entry unambiguously. An object class is a collection of attributes (or an attribute container) and may be defined within a schema. An object class may be a part of an object class hierarchy in which case it inherits all the properties of its parents.
FIG. 2 provides a diagram presenting object classes to represent equipment (or other inventory/assets) of a company. In this example 200, Monitor 220 is the child of Equipment 215, which is the child of Top 210 (e.g., the Abstract object class that terminates every object class hierarchy). An object class can be Structural, Auxiliary, or Abstract. Abstract classes are not instantiated by themselves but, instead, are only inherited by other classes. Structural classes derive from an inheritance chain that leads to object class Top 210. Structural classes do not inherit from Auxiliary classes, and Auxiliary classes do not inherit from Structural classes.
An object class has a globally unique name or identifier and is, as well as being an attribute container, also an attribute and may be searched on. An object class defines its member attributes and whether these must (i.e., mandatory) be present or may (i.e., optional) be present in an entry. One or more object class(es) must be present in an LDAP entry. Each object class supported by a LDAP server forms part of a collection called object classes, which can be discovered via the subsehema. An example of an object is where instances of an object class are an entry. Again, objects (or entries) in a LDAP directory or tree have a “reference”, a DN (distinguished name such as DN: uid=joe, ou=group, dc=example, dc=com). The DN uniquely identifies or references a particular object with uid=joe, belonging to organizational unit=‘group’ in a particular domain component “dc=example, dc=com.” The diagram 200 shown in FIG. 2 presents the object classes to represent equipment at a company including monitors, printers, and computers. As shown an object class monitor 220 can have several attributes (e.g., brand, type, and the like) and inherits attributes from an object class equipment 215. The equipment object class 215 can have mandatory attributes (e.g., the serial_no attribute is shown to be a must) that will be inherited by monitor 220. In this example, the description attribute of the object class equipment 215 is not mandatory but will also be inherited by the object class monitor 220.
While LDAP directory services are growing in use, there are a number of limitations with storing the directory information data, updating and manipulating the direction data, and searching the data with a variety of methods (e.g., the LDAP protocol is optimized for particular read processes). A specific concern is that with the representation of the information or data in a LDAP directory tree structure the data cannot normally be accessed by means of database techniques such as via Structured Query Language (SQL). SQL is a standardized language for modifying and asking questions in a relational database that has been widely adopted. Hence, the information technology and data storage industry has been searching for ways to provide access to LDAP-represented data for a relational database.
Efforts have been made to represent a directory service naming hierarchy with relational tables, but these have not been widely adopted. For example, U.S. Pat. No. 6,085,188 to Bachmann et al. implements LDAP using a DB/2 backing store, and mapping is provided between a naming directory and parent and ancestor relation tables. Although this work attempts to provide faster and more efficient directory service search capabilities, implementation is very complicated and searches require very complex search queries. Designers of directory services continue to look for simpler solutions to facilitate searching and/or access to data stored in an information directory such as a LDAP directory tree structure. It may be useful for such solutions to utilize less storage to provide relational tables mapped to the tee structure while still adequately representing data of a LDAP or other tree in a relational database to facilitate searching with less complex search queries.